本篇內容

• 介紹 Yacc語法中的Ambiguity and Conflicts

前言

我們昨天好不容易完成了連續加減法的計算機實作，編譯時卻出現以下的警告訊息：

yacc.y: conflicts: 4 shift/reduce

別緊張！一般人在寫程式的時候，總是有不小心出錯的時候。跟寫C++一樣，當bug比較嚴重的時候會直接導致編譯失敗，而比較小的問題，像是定義不清楚之類的模糊地帶，雖不至於到無法編譯，但編譯器會顯示警告訊息(Warning)，在程式運行到該階段，可能會導致無法預期的結果。

Ambiguity and Conflicts

在Yacc中，若是我們定義的規則不夠清楚，或是多個規則彼此出現衝突的時候，編譯器便會顯示警告訊息。

這兩種情況恰好對應到Yacc的兩個重要概念，「歧義性」（ambiguity）和「衝突」（conflict）

1. 歧義性（Ambiguity）： 歧義性指的是語法規則導致多種解釋的情況，使解析器無法明確地決定如何解析特定的輸入。換句話說，存在多個可能的解析樹，而解析器無法確定哪個是正確的。
2. 衝突（Conflict）： 衝突指的是解析器在根據語法規則進行解析時無法決定下一個動作的情況。Yacc 通常遇到的兩種主要衝突類型是「移入/歸納衝突」（shift/reduce conflict）和「歸納/歸納衝突」（reduce/reduce conflict）。
   • 移入/歸納衝突：當解析器可以選擇將下一個記號移入（shift）堆疊，或者歸納（reduce）已經在堆疊上的記號時，就會發生此類衝突。解析器不知道該採取哪個動作。
   • 歸納/歸納衝突：當解析器必須在兩個或多個不同的規則之間進行選擇時，就會發生歸納/歸納衝突。解析器無法確定應該使用哪個規則。

在進行語法設計時，需要小心處理歧義性和衝突，以確保解析器可以正確地解析輸入。通常，解決衝突的方法包括重新設計語法規則以消除歧義性，或者使用解析器生成器提供的優先級和關聯性規則來明確指定解析的方向。解決歧義性和衝突是編譯器設計中的重要挑戰之一。

聽起來好像還是不太清楚？我們實際來看看幾個衝突的例子。

shift/reduce conflict

當字串組同時匹配到shift跟reduce操作，此時系統不知道要做shift還是reduce。

我們拿昨天的計算機當作例子：

expr:
      NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    ;

在這個語法中，我們允許表達式包含加法和簡法運算符，但是沒有指定它們的優先順序。這就是可能引起 "shift/reduce conflict" 的地方。

現在考慮以下輸入：2 + 3 - 4。

當解析器讀取這個輸入時，它會在 2 + 之後遇到 3，此時解析器必須做出決策：

• 移入（Shift）：將 3 移入堆疊，然後處理 - 跟 4。
• 歸納（Reduce）：根據規則 expr : expr '+' expr 歸納 2 + 3 為一個更大的表達式。

這個決策點導致了 "shift/reduce conflict"，因為解析器不知道應該選擇哪個動作。如果我們要求解析器先處理加法，那麼這個表達式的結果應該是 (2 + 3) - 4；但如果我們要求解析器先處理減法，那麼結果應該是 2 + (3 - 4)。由於缺乏優先順序規則，解析器無法決定應該選擇哪個動作。

💡 當發生shift/reduce conflict，預設的情況下，Yacc會選擇shift操作

reduce/reduce conflict

當字串組同時有兩種方式可以reduce，此時系統不知道要用哪一種方式reduce。

我們來看以下例子：

expr: adder
		| NUMBER
    ;

adder: NUMBER
     ;

在這個語法中，當我們讀取到NUMBER的時候，有兩種方式可以做reduce: 化簡成adder或expr。

這個決策點導致了 "reduce/reduce conflict"，因為解析器不知道應該如何化簡。

💡 當發生reduce/reduce conflict，預設的情況下，Yacc會選擇較早被定義的語法規則。

找出規則衝突

我們可以使用以下的指令來產生衝突訊息：

bison -v yacc.y

這個指令可以讓Yacc產生一個yacc.output檔案，說明產生語法衝突的地方。

我們拿之前的計算機為例，產生出的output檔案部分內容如下：

State 8 conflicts: 2 shift/reduce
State 9 conflicts: 2 shift/reduce

Grammar

    0 $accept: func $end

    1 func: expr '='

    2 expr: NUMBER
    3     | expr '+' expr
    4     | expr '-' expr

這裡明確指出，在步驟8跟9會產生shift/reduce conflict。

接著，是每一個步驟的內容。
我們直接來看步驟8：

state 8

    3 expr: expr . '+' expr
    3     | expr '+' expr .
    4     | expr . '-' expr

    '+'  shift, and go to state 6
    '-'  shift, and go to state 7

    '+'       [reduce using rule 3 (expr)]
    '-'       [reduce using rule 3 (expr)]
    $default  reduce using rule 3 (expr)

這裡明確指出，當遇到expr '+' expr的時候，可以選擇shift(go to state 6) 或reduce (reduce using rule 3 (expr))

結語

今天我們介紹了語法衝突，並且可以透過編譯器顯示衝突的詳細資訊，幫助我們debug。

參考資料

• Ambiguity and Conflicts
• 5.6 Reduce/Reduce Conflicts